All the experiments are conducted on NVIDIA GTX 680 with pinned memory.

\subsection{Workloads}
To understand how different query characteristics affect query performance on GPU,
we focus on four warehousing operators: selection, join, aggregation and sort,
and study them independently.
For each operator, we identify the major factors that may affect its performance on GPU and 
conduct intensive experiments using synthetic data sets to understand their impacts.
When studying one factor, we keep other factors
as simple as possible to minimize their interference on query performance.

Different workloads are needed to study different factors of each operator.
For each operator, the workloads have similar format, only differing in the factors to study.
We only describe the default workload for each operator and the performance factors we study.
Readers can easily figure out the tested workloads for each factor.
For example, when studying factor A, we only vary A in the default workload.
However, since some factors are not independent from each other, when varying one factor,
the other factor may also vary.
We will clarify these factors in the description of the workloads.

\subsubsection{Selection}

The workload to study selection performance is represented as follows:
\\
\\
\textbf{select} L1, L2 ... \textbf{from} R \\
\textbf{where} predicates;
\\

In the experiments the default selection workload is configured as:
1 projected column,
1 predicate with simple less than comparison,
selectivity is 10\%,
the number of tuples in the table is 40 million,
and the types of all columns are integers.
The projected columns are not in the where predicates. 

The following factors are studied:
selectivity,
the number of projected columns,
the attribute size of the projected column,
and the number of predicates.

For the factor \textit{the number of prediates}, the predicates
are in the form of conjuction and the selectivity of each predicate
is 10\%.
When the number of predicates varies, the overall selectivity
varies correspondingly.


\subsubsection{Join}

The workload to study join performance is represented as follows:
\\
\\
\textbf{select} R1, R2 ..., S1, S2 ... \textbf{from} R, S\\
\textbf{where} R.key = S.key;
\\

In the experiments the default join workload is configured as:
1 projected column from fact table,
1 projected column from dimension table,
selectivity is 10\%,
the number of tuples in the dimension table is 5 million,
the number of tuples in the fact table is 80 million,
and the types of all columns are integers.
The join keys are not projected in the join results.

The following factors are studied independently:
selectivity,
the number of tuples in the dimension table,
the attribute size of the project column,
the number of projected columns from fact table,
and the number of projected columns from dimension table.

\subsubsection{Aggregation}

The workload to study aggregation performance is represented as follows:
\\
\\
\textbf{select} keys, aggFunc(L1), aggFunc(L2) ... \textbf{from} R \\
\textbf{group by} keys;
\\

In the experiments the default aggregation workload is configured as:
1 aggregation column to calculate for the aggregation function \textit{sum},
the number of tuples in the table is 20 million,
the number of distinct keys is 0.2 million,
and the types of all columns are integers.

The following factors are studied independently:
the width of the group by keys,
the number of distinct group by keys
and the number of aggregation columns.

\subsubsection{Sort}

The workload to study sort performance is represented as follows:
\\
\\
\textbf{select} keys, L1, L2 ... \textbf{from} R \\
\textbf{order by} keys;
\\

In the experiments the default sort workload is configured as:
1 projected column of all integers,
the number of tuples is 2 million, 
and the order by keys are all integers.

The following factors are studied independently:
the width of the sort keys,
and the number of projected columns.




\subsection{Execution Time Breakdown}

\begin{figure*}[ht]
\centering
\subfigure[Selection Time Breakdown]{
	\includegraphics[width=1.2in,height=1.6in,angle=270]{graph/exp/select/breakdown.ps}
	\label{fig:selectbreakdown}
}
\subfigure[Join Time Breakdown]{
	\includegraphics[width=1.2in,height=1.6in,angle=270]{graph/exp/join/breakdown.ps}
	\label{fig:joinbreakdown}
}
\subfigure[Agg Time Breakdown]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/agg/breakdown.ps}
	\label{fig:aggbreakdown}
}
\subfigure[Sort Time Breakdown]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/sort/breakdown.ps}
	\label{fig:sortbreakdown}
}
\begin{comment}
\subfigure[Join Memory Access]{
	\includegraphics[width=1.2in,height=1.6in,angle=270]{graph/exp/join/mem.ps}
	\label{fig:joinmem}
}
\begin{comment}
\subfigure[Agg Memory Access]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/agg/mem.ps}
	\label{fig:aggmem}
}
\subfigure[Sort Memory Access]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/sort/mem.ps}
	\label{fig:sortmem}
}
\end{comment}
\vspace{-0.15in}
%\caption {Execution time breakdown and GPU device memory characteristics for query operators}
\caption {Execution time breakdown for query operators}
\label{fig:breakdown}
\end{figure*}

\begin{figure*}[ht]
\centering
\subfigure[Kernel Execution Time]{
	\includegraphics[width=1.2in,height=1.6in,angle=270]{graph/exp/select/totalTime.ps}
	\label{fig:selecttime}
}
\subfigure[\# of Memory Transactions]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/select/totalMem.ps}
	\label{fig:selecttotalmem}
}
\vspace{-0.15in}
%\caption {Execution time breakdown and GPU device memory characteristics for query operators}
\caption {Kernel Execution and Memory Transactions for Selection}
\label{fig:kernelmem}
\end{figure*}





\begin{figure*}[ht]
\centering

\subfigure[Selectivity (\%)]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/select/5.ps}
	\label{fig:select5}
}
\subfigure[\# of projected columns]{
	\includegraphics[width=1.2in,height=1.6in,angle=270]{graph/exp/select/1.ps}
	\label{fig:select1}
}
\subfigure[Projected column width]{
	\includegraphics[width=1.2in,height=1.6in,angle=270]{graph/exp/select/2.ps}
	\label{fig:select2}
}
\subfigure[\# of Predicates]{
	\includegraphics[width=1.2in,height=1.6in,angle=270]{graph/exp/select/3.ps}
	\label{fig:select3}
}
\vspace{-0.15in}
\caption {Selection performance for different query characteristics}
\label{fig:select}
\vspace{-0.15in}
\end{figure*}

\begin{figure*}[ht]
\centering
\subfigure[Selectivity (\%)]{
	\includegraphics[width=1.2in,height=1.6in,angle=270]{graph/exp/join/1.ps}
	\label{fig:join1}
}
\subfigure[\# of fact columns]{
	\includegraphics[width=1.2in,height=1.6in,angle=270]{graph/exp/join/2.ps}
	\label{fig:join2}
}
\subfigure[\# of dim columns]{
	\includegraphics[width=1.2in,height=1.6in,angle=270]{graph/exp/join/3.ps}
	\label{fig:join3}
}
\subfigure[Dim column width]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/join/6.ps}
	\label{fig:join6}
}
\begin{comment}
\subfigure[Attribute Size of Fact Table]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/join/7.ps}
	\label{fig:join7}
}
\end{comment}
\vspace{-0.18in}
\caption {Join performance for different query characteristics}
\label{fig:join}
\vspace{-0.12in}
\end{figure*}


\begin{figure*}[ht]
\centering
\subfigure[Groupby key width]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/agg/1.ps}
	\label{fig:agg1}
}
\begin{comment}
\subfigure[Number of Distinct keys(\%)]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/agg/2.ps}
	\label{fig:agg2}
}
\end{comment}
\subfigure[\# of agg columns]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/agg/3.ps}
	\label{fig:agg3}
}
\subfigure[Sorted key width]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/sort/1.ps}
	\label{fig:sort1}
}
\subfigure[\# of sort columns]{
	\includegraphics[width=1.2in,height=1.6in, angle=270]{graph/exp/sort/2.ps}
	\label{fig:sort2}
}
\vspace{-0.2in}
\caption {Aggregation and sort performance for different query characteristics}
\label{fig:aggsort}
\vspace{-0.25in}
\end{figure*}


To understand the behavior of each query operator,
we breakdown the execution time of running each operator's default
workload on GPU into PCIe host to device transfer time (HtoD),
PCIe device to host transfer time (DtoH),
and kernel
execution time, which is further divided based on each query operator's
major kernel operations. For each kernel operation,
we also measure the number of issued GPU device memory access requests
and the number of actual memory access transactions
happened in the device.
The difference between these two numbers indicates
the corresponding kernel operation's memory access pattern 
and the utilization of the GPU device memory bandwidth.
In the ideal case, the number of issued memory requests 
is the same as the number of actual memory access transactions that happen in GPU,
which indicates a good memory access pattern and a high utilization
of GPU device's memory bandwidth.
For example, when a query sequentially scans an integer column, the GPU device
memory accesses can be coalesced and the two numbers are the same. 
On the other hand, when a query's access pattern of GPU device memory becomes irregular,
the number of actual memory transactions becomes larger than the issued memory requests.
The larger the differences,
the poorer utilization of GPU device memory bandwidth.

The breakdown of execution is shown in Figure \ref{fig:breakdown}.
Figure \ref{fig:kernelmem} shows the kernel execution time and the number of total memory transactions
for selection operator when we vary the number of projected columns from the default workload. 
As can be seen, the execution time of a kernel is correlated to the number of total memory transactions.

When considering the PCIe data transfer time and the kernel execution time,
the access frequency of the transferred data and the data access pattern determine the ratio of the
kernel execution time in the total execution time.
For selection operator, the PCIe transferred data are only accessed once,
and most of the data accesses are coalesced. Only generating selection results access the device memory
in an irregular way,
where more write transactions are generated than the number of write requests.
In this case, most of the execution time are spent on PCIe data transfer.
Things are different for join, aggregation and sort.
For join operator, although most of the transferred data are still accessed once, a relative large portion
of these data accesses, to be more specific, the read accesses to probe hash table
, are random which generates much more read transactions
than read requests. This makes kernel execution time comparable
to PCIe transfer time for join operator.
The portion of irregular data accesses in the total number of data accesses
is further increased for aggregation operator.
which makes more time spent on kernel execution than on PCIe transfer.
Sort operation also spends more time on kernel execution, shown in Figure \ref{fig:sortbreakdown}.
The reason is that when merging sort keys data are accessed multiple times.
This explains why the execution time of sort is dominated by kernel execution.

\subsection{Performance Variants}

To investigate the impacts of query characteristics on query performance, 
we vary different query characteristics from the default workloads
and study their performance.
The results are shown from Figure \ref{fig:select} to Figure \ref{fig:aggsort}.

For selection operator, PCIe data transfer time dominates the execution time in all cases, as shown in Figure \ref{fig:select},
which indicates that selection only query is a very expensive operation on GPU.
Among all query characteristics, selectivity is the only one that has relative less impact on 
PCIe data transfer but more on kernel execution.
This is because increasing selectivity will increase the amount of selection results written to device memory
which is accessed in an irregular way.

For join, we observe that query characteristics have different impacts on the PCIe data
transfer time and kernel execution time.
Varying characteristics related to fact table, which include the number of projected columns and the width 
of projected column , will have larger impact on PCIe data transfer than kernel execution,
as shown in Figure \ref{fig:join2}.
On the other hand, varying characteristics related to dimension table
will impact more on kernel execution than
on PCIe data transfer, as seen in Figure \ref{fig:join3} and Figure \ref{fig:join6}.
This is due to the random access of the dimension table in join operator.
For join selectivity, it has a greater impact on kernel execution time.
As selectivity increases, the number of random read when probing hash table,
and the number of join results that are randomly written to GPU device memory, are increased at the same time. 
This will significantly increase the kernel execution time.

Similarly, for aggregation and sort, when the query characteristics
affect the kernel operation that either accesses the transferred data multiple times, or accesses the
data in an irregular way, they will have more impacts on kernel execution
than PCIe data transfer, as is the case for 
the width of the sorted key shown in Figure \ref{fig:sort1}, and
the number of aggregated columns shown
in Figure \ref{fig:agg3}.
Otherwise, they will have more impacts on PCIe data transfer than on kernel execution,
as the width of the aggregation keys shown in Figure \ref{fig:agg1} and the number of projected
columns for sort shown in Figure \ref{fig:sort2}.

